﻿// Copyright (c) 2006, Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//
// Author: arvin.chen
//
//

#ifndef ALGORITHM_SORT_RADIX_H_
#define ALGORITHM_SORT_RADIX_H_
#include <algorithm>
#include <functional>

#ifndef ALGORITHM_SORT_BASE_H_
#include "algorithm/sort/base.h"
#endif

namespace algorithm {
	namespace sort {
		class Radix : public Base<int> {
		public:

			/**
			* Construction
			*
			* @param
			* @return
			*/
			Radix() :
				Base<int>::Base(kRadix)
			{
				
			}

			/**
			* Destruction
			*
			* @param VOID
			* @return
			*/
			~Radix()
			{

			}

			/**
			* sort
			*
			* @param int arr[]
			* @param int len
			* @return int
			*/
			virtual int* sort(int arr[], int len)
			{
				if (nullptr == arr || 1 >= len) return arr;

				int radix_bit = max_bit(arr, len);
				int *tmp = new int[len];
				int *count = new int[kRadixBit]; //Counter
				int i, j, k;
				int radix = 1;
				for (i = 1; i <= radix_bit; i++) //Sort d times
				{
					for (j = 0; j < kRadixBit; j++)
						count[j] = 0; //Clear the counter before each allocation
					for (j = 0; j < len; j++)
					{
						k = (arr[j] / radix) % 10; //Count the number of records in each bucket
						count[k]++;
					}
					for (j = 1; j < kRadixBit; j++)
						count[j] = count[j - 1] + count[j]; // assign the position in tmp to each bucket in turn
					for (j = len - 1; j >= 0; j--) // Collect all the records in the bucket into tmp in turn
					{
						k = (arr[j] / radix) % kRadixBit;
						tmp[count[k] - 1] = arr[j];
						count[k]--;
					}
					for (j = 0; j < len; j++) //Copy the contents of the temporary array to data
						arr[j] = tmp[j];
					radix = radix * kRadixBit;
				}
				delete[]tmp;
				delete[]count;

				return arr;
			}

		protected:
			/**
			* Assignment
			*
			* @param const Radix& cbase
			* @return Radix&
			*/
			Radix& operator=(const Radix& cbase);

			/**
			* Copy Construction
			*
			* @param const Radix& cbase
			* @return
			*/
			Radix(const Radix& cbase);

		private:
			/**
			* QuickArr
			* Get the position of the axis element
			*
			* @param T arr[]
			* @param int len
			* @return int
			*/
			int max_bit(int arr[], int len) //Auxiliary function, find the maximum number of bits of data
			{
				if (nullptr == arr || 0 >= len) return 0;
				int max_data = arr[0]; ///< maximum number
				/// First find the maximum number, and then find its digits, so that the original digits are judged for each number in turn, which is slightly optimized.
				for (int i = 1; i < len; ++i) {
					if (max_data < arr[i])
						max_data = arr[i];
				}
				int bit = 1;
				while (max_data >= kRadixBit) {
					max_data /= kRadixBit;
					++bit;
				}
				return bit;
			}

		public:
		protected:
		private:
			static const int kRadixBit = 10;

		};
	} // namespace algorithm 
} // namespace sort


#endif  // ALGORITHM_SORT_RADIX_H_
